#!/usr/bin/env python
# encoding: utf-8
'''
@author: Excelsiorly
@license: (C) Copyright 2022, All Rights Reserved.
@contact: excelsiorly@qq.com
@file: 043. 字符串相乘.py
@time: 2022/1/22 15:34
@desc: https://leetcode-cn.com/problems/multiply-strings/
> 给定两个以字符串形式表示的非负整数 num1 和 num2，返回 num1 和 num2 的乘积，它们的乘积也表示为字符串形式。
注意：不能使用任何内置的 BigInteger 库或直接将输入转换为整数。

@解题思路：
    1. 硬算
    2. Ot(mn+n2),其中 m 和 n 分别是num1, num2,需要从右往左遍历num2,对于num2的每一位,
        都需要和num1的每一位计算乘积，因此计算乘积的总次数是mn,
        字符串相加操作共有 n 次，相加的字符串长度最长为 m+n
        Os(m+n)
'''

class Solution(object):
    def multiply(self, num1, num2):
        """
        :type num1: str
        :type num2: str
        :rtype: str
        """
        def add(n1, n2):
            if len(n1)<len(n2): n1, n2 = n2, n1
            len1, len2 = len(n1), len(n2)
            res = []
            # 进位
            up = 0
            i = 0
            while i<len2:
                tmp = int(n1[i]) + int(n2[i]) + up
                res.append(str(tmp%10))
                up = tmp//10
                i += 1
            while i<len1:
                tmp = int(n1[i]) + up
                res.append(str(tmp%10))
                up = tmp//10
                i +=1
            if up>0:
                res.append(str(up))
            return res

        if num1=='0' or num2=='0': return '0'
        ans = None
        if len(num1)<len(num2): num1, num2 = num2, num1
        m, n = len(num1), len(num2)
        # 挨个按位做乘法
        for j in range(n-1, -1, -1):
            # 进位
            up = 0
            # 结果存储
            cur = []
            # 补0
            if j<n-1:
                for _ in range(n-1-j): cur.append('0') # 倒序遍历
            for i in range(m-1, -1, -1):
                tmp = int(num1[i]) * int(num2[j]) + up
                cur.append(str(tmp%10))
                up = tmp//10
            if up>0: cur.append(str(up))
            # 结果相加
            if not ans:
                ans = cur
            else:
                ans = add(cur, ans)

        return ''.join(ans[::-1])

if __name__ == '__main__':
    res = Solution().multiply('123', '456')
    print(res)